#include "Heap.h"

template<typename T>
Heap<T>::Heap()
{
	this->size = 0;
}

template<typename T>
Heap<T>::~Heap()
{
}

template<typename T>
void Heap<T>::pushElement(T & node)
{
	this->data[this->size++] = node;

	int i, j;
	T temp;
	i = size - 1;
	while (i > 0)
	{
		int j = (i - 1) / 2;
		if (data[i] < data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			i = j;
		}
		else
		{
			break;
		}
	}
}

template<typename T>
T& Heap<T>::getTop()
{
	if (size <= 0)
	{
		return nullptr;
	}

	T top = data[0];
	data[0] = data[--size];

	int j;
	bool swap;
	T temp;
	for (int i = 0; i <= (size - 2) / 2; i++) 
	{
		swap = false;
		j = i * 2 + 1;
		if (data[i] > data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			swap = true;
		}
		j = i * 2 + 2;
		if (data[i] > data[j])
		{
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
			swap = true;
		}
		if (!swap)
		{
			break;
		}
	}

	return top;
}
